#define _CRT_SECURE_NO_WARNINGS 2
#pragma once
#include<cstdio>
#include<iostream>
#include<cstdlib>

using namespace std;

typedef int DataType;

typedef struct QueueNode
{
	DataType val;
	struct QueueNode* next;
}Node;

typedef struct Queue
{
	QueueNode* front;
	QueueNode* back;
	int capacity;
}Queue;

void QInit(Queue* q)
{
	q->back = nullptr;
	q->front = nullptr;
	q->capacity = 0;
}

void QDestroy(Queue* q)
{
	Node* cur = q->front;
	while (cur)
	{
		Node* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	q->back = q->front = nullptr;
	q->capacity = 0;
}

void QPush(Queue* q,DataType val)
{
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->val = val;
	newnode->next = nullptr;
	if (q->front == nullptr)
		q->front = q->back=newnode;
	else
	{
		q->back->next = newnode;
		q->back = newnode;
	}
	q->capacity++;
}

void QPop(Queue* q)
{
	if (q->back == q->front)
	{
		free(q->back);
		q->back = q->front = nullptr;
	}
	else
	{
		Node* tmp = q->front->next;
		free(q->front);
		q->front = tmp;
	}
	q->capacity--;
}

bool QIsEmpty(Queue* q)
{
	return q->capacity == 0;
}

int size(Queue* q)
{
	return q->capacity;
}

void QPrint(Queue* q)
{
	Node* cur = q->front;
	while (cur)
	{
		cout << cur->val << " ";
		cur = cur->next;
	}
	putchar('\n');
}

